#include <stddef.h>
#include <string.h>

#define SS (sizeof(size_t))
#define ALIGN (sizeof(size_t) - 1)
#define ONES ((size_t)-1 / UCHAR_MAX)
#define HIGHS (ONES * (UCHAR_MAX / 2 + 1))
#define HASZERO(x) (((x)-ONES) & ~(x)&HIGHS)

int isspace(int c)
{
	return c == ' ' || (unsigned)c - '\t' < 5;
}

int isdigit(int c)
{
	return (unsigned)c - '0' < 10;
}

int atoi(const char *s)
{
	int n = 0, neg = 0;
	while (isspace(*s))
		s++;
	switch (*s) {
	case '-':
		neg = 1;
	case '+':
		s++;
	}
	/* Compute n as a negative number to avoid overflow on INT_MIN */
	while (isdigit(*s))
		n = 10 * n - (*s++ - '0');
	return neg ? n : -n;
}

void *memset(void *dest, int c, size_t n)
{
	char *p = dest;
	for (int i = 0; i < n; ++i, *(p++) = c)
		;
	return dest;
}

int strcmp(const char *l, const char *r)
{
	for (; *l == *r && *l; l++, r++)
		;
	return *(unsigned char *)l - *(unsigned char *)r;
}

int strncmp(const char *_l, const char *_r, size_t n)
{
	const unsigned char *l = (void *)_l, *r = (void *)_r;
	if (!n--)
		return 0;
	for (; *l && *r && n && *l == *r; l++, r++, n--)
		;
	return *l - *r;
}

size_t strlen(const char *s)
{
	const char *a = s;
	typedef size_t __attribute__((__may_alias__)) word;
	const word *w;
	for (; (uintptr_t)s % SS; s++)
		if (!*s)
			return s - a;
	for (w = (const void *)s; !HASZERO(*w); w++)
		;
	s = (const void *)w;
	for (; *s; s++)
		;
	return s - a;
}

void *memchr(const void *src, int c, size_t n)
{
	const unsigned char *s = src;
	c = (unsigned char)c;
	for (; ((uintptr_t)s & ALIGN) && n && *s != c; s++, n--)
		;
	if (n && *s != c) {
		typedef size_t __attribute__((__may_alias__)) word;
		const word *w;
		size_t k = ONES * c;
		for (w = (const void *)s; n >= SS && !HASZERO(*w ^ k);
		     w++, n -= SS)
			;
		s = (const void *)w;
	}
	for (; n && *s != c; s++, n--)
		;
	return n ? (void *)s : 0;
}

size_t strnlen(const char *s, size_t n)
{
	const char *p = memchr(s, 0, n);
	return p ? p - s : n;
}

char *stpcpy(char *restrict d, const char *s)
{
	typedef size_t __attribute__((__may_alias__)) word;
	word *wd;
	const word *ws;
	if ((uintptr_t)s % SS == (uintptr_t)d % SS) {
		for (; (uintptr_t)s % SS; s++, d++)
			if (!(*d = *s))
				return d;
		wd = (void *)d;
		ws = (const void *)s;
		for (; !HASZERO(*ws); *wd++ = *ws++)
			;
		d = (void *)wd;
		s = (const void *)ws;
	}
	for (; (*d = *s); s++, d++)
		;
	return d;
}

char *stpncpy(char *restrict d, const char *s, size_t n)
{
	typedef size_t __attribute__((__may_alias__)) word;
	word *wd;
	const word *ws;
	if (((uintptr_t)s & ALIGN) == ((uintptr_t)d & ALIGN)) {
		for (; ((uintptr_t)s & ALIGN) && n && (*d = *s); n--, s++, d++)
			;
		if (!n || !*s)
			goto tail;
		wd = (void *)d;
		ws = (const void *)s;
		for (; n >= sizeof(size_t) && !HASZERO(*ws);
		     n -= sizeof(size_t), ws++, wd++)
			*wd = *ws;
		d = (void *)wd;
		s = (const void *)ws;
	}
	for (; n && (*d = *s); n--, s++, d++)
		;
tail:
	memset(d, 0, n);
	return d;
}

char *basename(char *s)
{
	size_t i;
	if (!s || !*s)
		return ".";
	i = strlen(s) - 1;
	for (; i && s[i] == '/'; i--)
		s[i] = 0;
	for (; i && s[i - 1] != '/'; i--)
		;
	return s + i;
}